package demo;

import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
import java.util.regex.Pattern;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}


class Solution {


    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean[] ints = solution.subsequenceSumAfterCapping(new int[]{14, 8, 9, 10, 13, 5, 15, 15, 1, 14, 3, 15, 2, 2, 15}, 35);
        System.out.println(Arrays.toString(ints));
    }

    public boolean[] subsequenceSumAfterCapping(int[] nums, int k) {
        int n = nums.length;
        boolean[] res = new boolean[n];
        boolean[] dp = new boolean[k + 1];
        dp[0] = true;
        // 将数组排序
        Arrays.sort(nums);
        int i = 0;
        //将数组分成2部分 第一部分
        for (int x = 1; x <= n; x++) {
            // 优先更新 nums[i] < x的内容
            while (i < n && nums[i] < x) {
                // 这里必须是倒着排序
                for (int j=k ; j >= 1; j--) {
                    // 只能选择投或者不投
                    if (j - nums[i] >= 0){
                        dp[j] = dp[j] || dp[j - nums[i]];
                    }
                }
                i++;
            }
            // 然后有剩余的几个i，则将剩余的i的数字加起来
            int l = n - i;
            boolean flag = false;
            for (int j = 0; j <= l; j++) {
                if (k - j * x >= 0) {
                    flag = dp[k - j * x] || flag;
                }
                if (flag) {
                    break;
                }
            }
            res[x - 1] = flag;
        }
        return res;
    }

//    public boolean[] subsequenceSumAfterCapping(int[] nums, int k) {
//        boolean[] res = new boolean[nums.length];
//        int n = nums.length;
//
//        int maxNums = -1;
//        for (int i = 0; i < nums.length; i++) {
//            int x = i + 1;
//            int maxSum = (i + 1) * n;
//            // 如果连最大的和小于k，则说明不管怎么组合都无法满足k,则返回false
//            if (maxSum < k) {
//                res[i] = false;
//            } else if (maxSum == k) {
//                res[i] = true;
//            } else {
//                // 否则，则需要计算当前数字的组合情况
//            }
//        }
//    }

    public int[] maxKDistinct(int[] nums, int k) {
        // 塞选出前k个不重复且最大的元素
        // 优先级队列
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            if (!queue.contains(nums[i])) {
                queue.add(nums[i]);
                if (queue.size() > k) {
                    queue.poll();
                }
            }
        }
        int length = queue.size();
        int[] topK = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            topK[i] = queue.poll();
        }
        return topK;
    }

    public long bowlSubarrays(int[] nums) {
        long res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // 这个是什么栈？
            // 如果栈不为空，并且栈顶元素小于当前元素，则栈顶元素出栈，并记录次数，次数等于栈顶元素在数组中的索引减去当前索引
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int index = stack.pop();
                if (i - index >= 2) {
                    res++;
                }
            }
            if (!stack.isEmpty() && i - stack.peek() >= 2) {
                res++;
            }
            stack.push(i);
        }
        return res;
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums2[i]) {
                stack.pop();
            }
            map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
            stack.push(nums2[i]);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]);
        }

        return res;
    }

    private static Map<Integer, Integer> map = new HashMap<>();
    private List<Integer> prefixSum = new ArrayList<>();

//    public int pathSum(TreeNode root, int targetSum) {
//        if (root == null) {
//            return 0;
//        }
//        prefixSum.add(0);
//    }
//
//    public int pathSum2(TreeNode root, int targetSum) {
//        if (root == null) {
//            return 0;
//        }
//
//    }


    /**
     * 打印二维数组
     *
     * @param a
     */
    private static void printArray(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

}